package com.wu;

/**
 * 希尔排序
 */
public class ShellSort {

    public static void shellSort(int[] array) {
        int exchange=0;
        System.out.println("当前需要排序数组长度为:" + array.length);
        int increment = array.length / 2;
        while (increment > 0) {
            // increment为增量，如果长度为偶数时为分组的数量，奇数时等于分组的数量-1
            System.out.println("increment=" + increment);
            for (int i = 0; i < increment; i++) {
                System.out.println("i=" + i);
                // 对分组的元素进行组内插入排序，当increment为1的时候是完完整整的插入排序
                for (int j = i + increment; j < array.length; j += increment) {
                    System.out.print("j=" + j + " ");
                    for (int k = j - increment; k >= 0; k -= increment) {
                        System.out.print("k=" + k + " ");
                        // 如果k比k+increment的数值大，则进行交换值
                        if (array[k] > array[k + increment]) {
                            int temp = array[k];
                            array[k] = array[k + increment];
                            array[k + increment] = temp;
                            System.out.print(k + "与" + (k + increment) + "交换值 ");
                            exchange++;
                        }
                    }
                    System.out.println();
                }
            }

            System.out.print("shellSort排序结果：");
            for (int i = 0; i < array.length; i++) {
                System.out.print(array[i] + " ");
            }
            System.out.println("共交换了"+exchange+"次");
            System.out.println();
            increment = increment / 2;
            System.out.println();
        }


    }

    public static void main(String[] args) {
        int[] array = new int[]{3, 9, 10, 4, 6, 5, 1, 7, 0};
        // 希尔排序
        shellSort(array);
        System.out.println("=======================================");
        int[] array2 = new int[]{3, 9, 10, 4, 6, 5, 1, 7, 0};
        // 插入排序
        insertSort(array2);
    }


    public static void insertSort(int[] array){
        int exchange = 0;
        for (int j = 0; j < array.length; j ++) {
            System.out.print("j=" + j + " ");
            for (int k = j - 1; k >= 0; k--) {
                System.out.print("k=" + k + " ");
                // 如果k比k+increment的数值大，则进行交换值
                if (array[k] > array[k + 1]) {
                    int temp = array[k];
                    array[k] = array[k + 1];
                    array[k + 1] = temp;
                    System.out.print(k + "与" + (k + 1) + "交换值 ");
                    exchange++;
                }
            }
            System.out.println();
        }
        System.out.print("insertSort排序结果：");
        for (int i = 0; i < array.length; i++) {
            System.out.print(array[i] + " ");
        }
        System.out.println("共交换了"+exchange+"次");
    }
}